package com.axzh.interview.algorithm;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 最近公共祖先
 * 
 * @author Administrator
 *
 */
public class LCA {

	private static final int MAX = 20;
	private static Map<Integer, List<Integer>> node = new HashMap<>();
	private static Map<Integer, List<Integer>> query = new HashMap<>();
	private static int[] ancestor = new int[MAX];
	private static int[] indegree = new int[MAX];
	private static int[] visit = new int[MAX];
	private static int[] f = new int[MAX];
	// private static int[] r = new int[MAX];

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 16;
		initTree(n);
		List<Integer> list = new ArrayList<>();
		list.add(4);
		indegree[4]++;
		list.add(3);
		indegree[3]++;
		list.add(0);
		indegree[0]++;
		node.put(7, list);

		list = new ArrayList<>();
		list.add(8);
		indegree[8]++;
		node.put(4, list);

		list = new ArrayList<>();
		list.add(5);
		indegree[5]++;
		list.add(9);
		indegree[9]++;
		node.put(3, list);

		list = new ArrayList<>();
		list.add(13);
		indegree[13]++;
		list.add(12);
		indegree[12]++;
		node.put(0, list);

		list = new ArrayList<>();
		list.add(14);
		indegree[14]++;
		list.add(6);
		indegree[6]++;
		node.put(5, list);

		list = new ArrayList<>();
		list.add(10);
		indegree[10]++;
		list.add(15);
		indegree[15]++;
		list.add(1);
		indegree[1]++;
		node.put(9, list);

		list = new ArrayList<>();
		list.add(2);
		indegree[2]++;
		list.add(11);
		indegree[11]++;
		node.put(15, list);

		int s, t;
		s = 8;
		t = 12;
		list = new ArrayList<>();
		list.add(t);
		query.put(s, list);

		list = new ArrayList<>();
		list.add(s);
		query.put(t, list);

		for (int i = 0; i < n; i++) {
			if (indegree[i] == 0) {
				lca(i);
				break;
			}
		}
	}

	private static void initTree(int n) {
		for (int i = 0; i < n; i++) {
			f[i] = 1;
			indegree[i] = 0;
			visit[i] = 0;
			ancestor[i] = 0;
			node.put(i, new ArrayList<Integer>());
			query.put(i, new ArrayList<Integer>());
		}
	}

	private static int find(int n) {
		if (f[n] == n) {
			return n;
		} else {
			f[n] = find(f[n]);
		}
		return f[n];
	}

	private static void union(int x, int y) {
		int a = find(x);
		int b = find(y);
		if (a != b)
			f[b] = a;
	}

	public static void lca(int root) {
		f[root] = root;
		int size = node.get(root).size();
		for (int i = 0; i < size; i++) {
			lca(node.get(root).get(i));
			union(root, node.get(root).get(i));
			ancestor[find(root)] = root;
		}
		visit[root] = 1;
		size = query.get(root).size();
		for (int i = 0; i < size; i++) {
			if (visit[query.get(root).get(i)] == 1) {
				System.out.println(ancestor[find(query.get(root).get(i))]);
				continue;
			}
		}
	}

}
